When computers were first built, the objective was to make programs run. There was no concern about making computers efficient: it was enough that they executed the programs written for the computers. Thus, the processor read an instruction and executed it, then went back to the program for the next instruction.
As more has become known about computer design, engineers have become able to design processors that are more efficient than simple “fetch and execute” processors. Modem processors include “pipelines”: at any moment, different parts of the processor are working on different instructions. For example, while the core of the central processing unit is executing an instruction, another part of the processor might be loading a data value from memory that will be needed by a future instruction.
One area of processor design that has received extensive study and thought is branch processing. Depending on an associated data value, after a branch instruction is executed, control may continue at one of two (or more) different points. This creates a problem for modern processors: until the outcome of the branch instruction is known, any preprocessing of later instructions may be in vain.
To account for this, modern processors perform branch prediction. Rather than waiting for the branch instruction to execute and the correct path through the program to be known, the processor makes a guess. But if the processor guesses incorrectly, any preprocessing along the projected path is wasted. For example, if both possible follow-up instructions to a branch instruction load a value into a register, if the wrong instruction is preprocessed, then the wrong value will be in the register. The processor must then unwind the preprocessing performed on the wrong path. If the processor guesses incorrectly, execution might be slower than if the processor had simply waited until the branch instruction was executed.
Rather than guessing blindly, branch predictors try to make educated guesses. To accomplish this, they make certain assumptions. One possible assumption is that the outcome at a particular branch instruction is dependent solely on the prior outcomes at that branch. Another, more general assumption is that the outcome is dependent on some (fixed size) set of instructions preceding the branch instruction. There are other variations.
FIG. 1 shows a computer system executing a program according to the prior art. In FIG. 1, computer system 105 includes computer 110, installed into which is memory 115. Loaded in memory 115 is program 130, a portion of which is shown in FIG. 1. Program 130 includes branch instruction 135.
Under the assumption that the most frequent direction taken for a branch is the most likely, using table 140, a branch predictor may predict whether a branch is taken or not. As shown in row 145, instruction 135 has branched more times than not (the counter is incremented each time the branch is taken, and decremented each time it is not). Thus, the branch predictor would guess that the branch will be taken again.
Under the assumption that the direction taken by a branch is affected by the preceding instructions, the branch predictor looks at instructions 150 (which include instruction 135) and hashes their program counters together. This produces an index that the branch predictor may use to access table 155. As indicated at row 160, using this approach, the branch predictor would guess that the branch will not be taken.
But consider a branch predictor that that looks at the last five instructions before the branch. There is no guarantee that any of these instructions have any impact on the data value that controls the outcome of the branch. Likewise, there is no guarantee that these instructions are the only instructions that affect a prediction. There might be an older instruction that is highly pertinent to the outcome of the branch.
A need remains for a way to more accurately predict branches and other properties of instructions, that addresses these and other problems associated with the prior art.